package algorithm;

/**
 * 快速排序，又称划分交换排序，简称快排
 * 1. 从待2排序的数列挑选一个元素，叫pivot
 * 2. 重新排序数列，使比pivot小的元素在pivot的左边，比pivot大的元素都在pivot右侧
 * 3. 递归执行步骤2，直至排序结束
 * 时间复杂度：最差O(N^2) 平均O(N*LogN)
 */
public class QuickSort implements ISort {
    @Override
    public void sort(int[] nums) {
        sort(nums, 0 , nums.length - 1);
    }

    private void sort(int[] nums, int low, int high) {

        if (low >= high) {
            return;
        }

        int i = low;
        int j = high;

        int base = nums[i];
        int temp;
        do {
            while (i < j && nums[j] > base) {
                j--;
            }

            while (i < j && nums[i] <= base) {
                i++;
            }

            if (i < j) {
                temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        } while (i != j);

        //交换base
        nums[low] = nums[i];
        nums[i] = base;

        sort(nums, low, i - 1);
        sort(nums, i + 1, high);
    }
}
